package cn.hesion.tmp;
/**
 * ClassName: RectangleArea <br/>
 * Description: <br/>
 * date: 2022/5/27 21:55<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

import java.util.*;

/**
 * 850. 矩形面积 II
 *
 * @author: hesion
 * @create: 2022-05-27 21:55
 **/
public class RectangleArea {
    static Long modNum = 1000000007L;
    List<VSeg> vs = new ArrayList<VSeg>();
    Set<Integer> Y = new TreeSet<Integer>((a, b) -> a - b);
    int[] compressY = null;


    public int rectangleArea(int[][] rectangles) {
        int i = 0;
        vs.clear();
        Y.clear();
        //<1>所有线段分为两个部分
        for (i = 0; i < rectangles.length; i++) {
            vs.add(new VSeg(rectangles[i][0], rectangles[i][1], rectangles[i][3], 1));
            vs.add(new VSeg(rectangles[i][2], rectangles[i][1], rectangles[i][3], -1));
            Y.add(rectangles[i][1]);
            Y.add(rectangles[i][3]);
        }

        //<2>

        vs.sort(new Comparator<VSeg>() {
            @Override
            public int compare(VSeg o1, VSeg o2) {
                return o1.x - o2.x;
            }
        });
        //<3> Y坐标离散化
        //<3.1> 去重排序，因为TreeSet在添加时已经做处理，这里无需处理，但需要将TreeSet转换成List，方便getIndex

        int range = 0;// 压缩坐标范围 && 编号
        compressY = new int[Y.size()];// 压缩坐标找原x坐标
        for (Integer num : Y) {
            compressY[range++] = num;
        }

        int m = Y.size() - 1;
        long ans = 0L;

        SegNode root = segtreeBuild(0, m);

        for (i = 0; i < vs.size();++i) {
            int l = vs.get(i).y1;
            int r = vs.get(i).y2;
            int val = vs.get(i).v;

            if (i != 0) {
                assert root != null;
                ans += (long) root.len * (vs.get(i).x - vs.get(i - 1).x);
                ans %= modNum;
            }
            segTreeInsert(root, getIndex(l), getIndex(r), 0, m, val);

        }

        return (int) ans;
    }

    private void segTreeInsert(SegNode root, int x, int y, int l, int r, int val) {
        if (isNotIntersect(x, y, l, r)) {
            return;
        }

        if (isContain(x, y, l, r)) {
            root.cover += val;
            updateRoot(root, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        segTreeInsert(root.left, x, y, l, mid, val);
        segTreeInsert(root.right, x, y, mid, r, val);
        updateRoot(root, l, r);
    }

    private void updateRoot(SegNode root, int l, int r) {
        if (root.cover > 0) {
            root.len = getValue(r) - getValue(l);
        } else {
            if (l + 1 == r) {
                root.len = 0;
            } else {
                mergeFromSon(root);
            }
        }
    }

    private void mergeFromSon(SegNode root) {
        root.len = root.left.len + root.right.len;
    }


    private boolean isContain(int x, int y, int l, int r) {
        return x <= l && y >= r;
    }

    private boolean isNotIntersect(int x, int y, int l, int r) {
        return y <= l || x >= r;
    }

    private int getIndex(int val) {
        int l = 0, r = Y.size() - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (compressY[mid] == val) {
                return mid;
            } else if (val > compressY[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    private int getValue(int idx) {
        return compressY[idx];
    }

    private SegNode segtreeBuild(int l, int r) {
        if (l >= r) {
            return null;
        }
        SegNode root = new SegNode();
        if (l + 1 == r) {
            return root;
        }
        int mid = (l + r) >> 1;
        root.left = segtreeBuild(l, mid);
        root.right = segtreeBuild(mid, r);
        return root;
    }


    public static void main(String[] args) {
        int i = new RectangleArea().rectangleArea(new int[][]{
                new int[]{0, 0, 2, 2},
                new int[]{1, 0, 2, 3},
                new int[]{1, 0, 3, 1}
        });
        System.out.println(i);
    }
}

class VSeg {
    int x;  //垂直线段X的坐标
    int y1, y2; //垂直线段的两个y坐标
    int v; //出入边标记 1 入 -1出

    public VSeg() {
    }

    public VSeg(int x, int y1, int y2, int v) {
        this.x = x;
        this.y1 = y1;
        this.y2 = y2;
        this.v = v;
    }

    @Override
    public String toString() {
        return "VSeg{" +
                "x=" + x +
                ", y1=" + y1 +
                ", y2=" + y2 +
                ", v=" + v +
                '}';
    }
}

class SegNode {
    SegNode left, right;
    int len;
    int cover;

    public SegNode() {
        left = right = null;
        len = 0;
        cover = 0;
    }
}